// Copyright (C) 2011 and onwards Noam Shazeer and Georges Harik

#include "hashthing.h"
#include "interpret.h"



bool IsHash(Thing h) {
  return (h.IsArray() && 
	  (h.ArraySize() != 0) && 
	  (h.ArraySize() % 3 == 0));
}

bool IsMutableHash(Thing h) { return IsHash(h) && h.IsMutable(); }

Thing & HashStatus(Thing h, Thing pos) { 
  return h.Ref(pos.GetInteger() * 3); 
}
Thing & HashKey(Thing h, Thing pos) { 
  return h.Ref(pos.GetInteger() * 3 + 1); 
}
Thing & HashValue(Thing h, Thing pos) { 
  return h.Ref(pos.GetInteger() * 3 + 2); 
}

Thing HashFind(Thing h, Thing key, ThreadAllocator *a) {
  int64 step = 1;
  int64 capacity = HashCapacity(h);
  Thing hash_value = HashToThing(&key, 1);
  Thing pos = Thing::MakeInteger(hash_value.GetInteger() % capacity);
  while (1) {
    Thing status = HashStatus(h, pos);
    if (status == NIL) return pos;
    Thing k = HashKey(h, pos);
    if (k == key) return pos;
    if (step > 20 && h.IsMutable()) { 
      GrowHash(h, a);
      return HashFind(h, key, a);
    }
    if (step > capacity) {
      if (h.IsMutable()) {
	GrowHash(h, a);
	return HashFind(h, key, a);
      }
      return ABSENT;
    }
    pos = Thing::MakeInteger((pos.GetInteger() + step) % capacity);
    step++;
  }
  CHECK(false);
  return NULL;
}
Thing HashLookDefault(Thing h, Thing key, Thing default_value, 
		      ThreadAllocator *a) {
  Thing pos = HashFind(h, key, a);
  if (pos == ABSENT) return default_value;
  Thing status = HashStatus(h, pos);
  if (status == PRESENT) return HashValue(h, pos);
  return default_value;
}
void HashSet(Thing h, Thing key, Thing value, ThreadAllocator *a) {
  CHECK(h.IsMutable());
  Thing pos = HashFind(h, key, a);
  CHECK(pos != ABSENT);
  HashStatus(h, pos) = PRESENT;
  HashKey(h, pos) = key;
  HashValue(h, pos) = value;
}
void HashDelete(Thing h, Thing key, ThreadAllocator *a) {
  CHECK(h.IsMutable());
  Thing pos = HashFind(h, key, a);
  if (pos == ABSENT) return;
  if (HashStatus(h, pos) == PRESENT) HashStatus(h, pos) = ABSENT;
}
void GrowHash(Thing h, ThreadAllocator *a) {
  int64 capacity = HashCapacity(h);
  Thing old = a->MakeMutableArray(h.ArraySize(), NIL);
  for (uint64 i=0; i<h.ArraySize(); i++)
    old.Ref(i) = h.Ref(i);
  a->ResizeMutableArray(h.GetBox(), 2 * h.ArraySize());
  for (uint64 i=0; i<h.ArraySize(); i++)
    h.Ref(i) = NIL;
  for (int64 i=0; i<capacity; i++) {
    Thing pos = Thing::MakeInteger(i);
    if (HashStatus(old, pos) == PRESENT) {
      HashSet(h, HashKey(old, pos), HashValue(old, pos), a);
    }
  }
}

HashIterator::HashIterator(Thing h) {
  h_ = h;
  pos_ = 0;
  AdvanceToNextPresent();
}

void HashIterator::AdvanceToNextPresent() {
  while (!AtEnd() && (GetStatus() != PRESENT)) pos_++;
}
